Route Preserving Stabilization
Identifieur interne : 007998 ( Main/Exploration ); précédent : 007997; suivant : 007999Route Preserving Stabilization
Auteurs : Colette Johnen [France] ; Sébastien Tixeuil [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: A distributed system is self-stabilizing if it returns to a legitimate state in a finite number of steps regardless of the initial state, and the system remains in a legitimate state until another fault occurs. A routing algorithm is loop-free if, a path being constructed between two processors p and q, any edges cost change induces a modification of the routing tables in such a way that at any time, there always exists a path from p to q. We present a self-stabilizing loop-free routing algorithm that is also route preserving. This last property means that, a tree being constructed, any message sent to the root is received in a bounded amount of time, even in the presence of continuous edge cost changes. Also, and unlike previous approaches, we do not require that a bound on the network diameter is known to the processors that perform the routing algorithm. We guarantee self-stabilization for many metrics (such as minimum distance, shortest path, best transmitter, depth first search metrics, etc.), by reusing previous results on r-operators.
Url:
DOI: 10.1007/3-540-45032-7_14
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001478
- to stream Istex, to step Curation: 001461
- to stream Istex, to step Checkpoint: 001988
- to stream Main, to step Merge: 007D77
- to stream Main, to step Curation: 007998
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Route Preserving Stabilization</title><author><name sortKey="Johnen, Colette" sort="Johnen, Colette" uniqKey="Johnen C" first="Colette" last="Johnen">Colette Johnen</name></author><author><name sortKey="Tixeuil, Sebastien" sort="Tixeuil, Sebastien" uniqKey="Tixeuil S" first="Sébastien" last="Tixeuil">Sébastien Tixeuil</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:59642B5095389C3C9A6EBCF159E2A0AA1473FCFE</idno><date when="2003" year="2003">2003</date><idno type="doi">10.1007/3-540-45032-7_14</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-F1K0GXGF-H/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001478</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001478</idno><idno type="wicri:Area/Istex/Curation">001461</idno><idno type="wicri:Area/Istex/Checkpoint">001988</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001988</idno><idno type="wicri:doubleKey">0302-9743:2003:Johnen C:route:preserving:stabilization</idno><idno type="wicri:Area/Main/Merge">007D77</idno><idno type="wicri:Area/Main/Curation">007998</idno><idno type="wicri:Area/Main/Exploration">007998</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Route Preserving Stabilization</title><author><name sortKey="Johnen, Colette" sort="Johnen, Colette" uniqKey="Johnen C" first="Colette" last="Johnen">Colette Johnen</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Recherche en Informatique, CNRS UMR 8623, Université Paris-Sud XI, F-91405, Orsay cedex</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Orsay</settlement></placeName></affiliation></author><author><name sortKey="Tixeuil, Sebastien" sort="Tixeuil, Sebastien" uniqKey="Tixeuil S" first="Sébastien" last="Tixeuil">Sébastien Tixeuil</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire de Recherche en Informatique, CNRS UMR 8623, Université Paris-Sud XI, F-91405, Orsay cedex</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Orsay</settlement></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Équipe Grand Large, INRIA Futurs</wicri:regionArea><wicri:noRegion>INRIA Futurs</wicri:noRegion><wicri:noRegion>INRIA Futurs</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A distributed system is self-stabilizing if it returns to a legitimate state in a finite number of steps regardless of the initial state, and the system remains in a legitimate state until another fault occurs. A routing algorithm is loop-free if, a path being constructed between two processors p and q, any edges cost change induces a modification of the routing tables in such a way that at any time, there always exists a path from p to q. We present a self-stabilizing loop-free routing algorithm that is also route preserving. This last property means that, a tree being constructed, any message sent to the root is received in a bounded amount of time, even in the presence of continuous edge cost changes. Also, and unlike previous approaches, we do not require that a bound on the network diameter is known to the processors that perform the routing algorithm. We guarantee self-stabilization for many metrics (such as minimum distance, shortest path, best transmitter, depth first search metrics, etc.), by reusing previous results on r-operators.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Île-de-France</li></region><settlement><li>Orsay</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Johnen, Colette" sort="Johnen, Colette" uniqKey="Johnen C" first="Colette" last="Johnen">Colette Johnen</name></region><name sortKey="Tixeuil, Sebastien" sort="Tixeuil, Sebastien" uniqKey="Tixeuil S" first="Sébastien" last="Tixeuil">Sébastien Tixeuil</name><name sortKey="Tixeuil, Sebastien" sort="Tixeuil, Sebastien" uniqKey="Tixeuil S" first="Sébastien" last="Tixeuil">Sébastien Tixeuil</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007998 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007998 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:59642B5095389C3C9A6EBCF159E2A0AA1473FCFE
|texte= Route Preserving Stabilization
}}
| This area was generated with Dilib version V0.6.33. |  |